package com.gorkr;

public class L712 {
    public static int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
//        int a1 =0;
//        int a2 =0;
//        for (int cnum: c1
//             ) {
//            a1 += cnum;
//        }
//        for (int cnum : c2
//                ) {
//            a2 += cnum;
//        }

        int[][] dp = new int[m+1][n+1];  // dp[i][j] 为s1[0...i] s2[0...j]删除最少所需
//
//        for (int i = 0; i <= m; i++) {
//            dp[i][0] = a1;
//        }
//        for (int i = 0; i <=n ; i++) {
//            dp[0][i] = a2;
//
//        }

        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = dp[i-1][0] + c1[i-1];
        }
        for (int i = 1; i <= s2.length(); i++) {
            dp[0][i] = dp[0][i-1] + c2[i-1];
        }



        dp[0][0] = 0;
        // 状态
        for (int i = 1; i <=m; i++) {

            for(int j=1; j<=n ; j++){
                if(c1[i-1]==c2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = getMin(dp[i][j-1]+(int)c2[j-1], dp[i-1][j]+(int)c1[i-1],dp[i-1][j-1]+(int)c1[i-1]+(int)c2[j-1]);
                }

            }
        }
        return dp[m][n];


    }
    public static int getMin(int a, int b, int c){

        return Math.min(Math.min(a,b),c);
    }

    public static void main(String[] args) {
        String s1 = "a";
        String s2 = "at";
        System.out.println( minimumDeleteSum(s1, s2));


    }
}
